/**
 * 
 */
package linkedlist.passed2;

import linkedlist.Node;
import utils.PrintUtils;

/**
 * @author Michael
 * 
 * @since 2013/01/18
 * @version 2013/01/18
 *
 */
public class ReverseLinkedList {

	public static <T extends Comparable<? super T>> Node<T> reverseLinkedListIterative(
			Node<T> head) {
		Node<T> newHead = null;
		while (head != null) {
			Node<T> next = head.next;
			head.next = newHead;
			newHead = head;
			head = next;
		}

		return newHead;
	}

	public static <T extends Comparable<? super T>> Node<T> reverseLinkedListRecursive(
			Node<T> head) {
		if (head == null || head.next == null)
			return head;

		Node<T> newHead = reverseLinkedListRecursive(head.next);
		head.next.next = head;
		head.next = null;

		return newHead;
	}

	/**
	Reverse Linked list II
	
	Reverse a linked list from position m to n. Do it in-place and in one-pass.
	
	For example:
	Given 1->2->3->4->5->NULL, m = 2 and n = 4,
	
	return 1->4->3->2->5->NULL.
	
	Note:
	Given m, n satisfy the following condition:
	1 ≤ m ≤ n ≤ length of list.
	
	  dummyNode->node-->head->node->...-> null
	             newHead newTail
	             
	  dummyNode->node<--newTail<-node<-newHead   head->node->...-> null
	            
	  dummyNode->node->newHead->node->newTail->head->node->...->null
	 */
	public static <T extends Comparable<? super T>> Node<T> reverseLinkedList2Iterative(
			Node<T> head, int m, int n) {

		Node<T> dummyHead = new Node<T>();
		dummyHead.next = head;

		// advance head to the mth - 1 node
		head = dummyHead;
		for (int i = 1; i < m; i++) {
			head = head.next;
		}

		Node<T> newHead = head; // newHead on m - 1 position
		head = head.next; // head on m position
		Node<T> newTail = head; // newTail on m position
		// reverse node from m to n
		for (int i = m; i <= n; i++) {
			Node<T> temp = head.next;
			head.next = newHead;
			newHead = head;
			head = temp;
		}

		// newHead on n position
		// head on n + 1 position
		// newTaill on m position, newTail next is m - 1 position
		newTail.next.next = newHead;
		newTail.next = head;

		return dummyHead.next;
	}

	/**
	Reverse Nodes in k-Group
	Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
	
	If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
	
	You may not alter the values in the nodes, only nodes itself may be changed.
	
	Only constant memory is allowed.
	
	For example,
	Given this linked list: 1->2->3->4->5
	
	For k = 2, you should return: 2->1->4->3->5
	
	For k = 3, you should return: 3->2->1->4->5

	 */
	// best for interview
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) 
            return head;
        
        int len = 0;
        ListNode node = head;
        while (node != null) {
        	len++;
        	node = node.next;
        }
        if (len < k) return head;
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        tail.next = head;
        for (int i = len; i >= k; i = i - k) {
            ListNode[] pair = reverseK(tail.next, k);
            tail.next = pair[0];
            tail = pair[1];
        }
        
        return dummyHead.next;
    }
    
    private ListNode[] reverseK(ListNode head, int k) {
    	ListNode newHead = head;
    	ListNode newTail = head;

    	for (int i = 0; i < k; i++) {
    		ListNode next = head.next;
    		head.next = newHead;
    		newHead = head;
    		head = next;
    	}
    	newTail.next = head;
   	
    	return new ListNode[] {newHead, newTail};
    }
    
    private ListNode[] reverseK1(ListNode head, int k) {
    	ListNode newHead = head;
    	// pitfall: only run k-1 loop
    	for (int i = 1; i < k; i++) {
    		ListNode temp = head.next;
    		head.next = temp.next;
    		temp.next = newHead;
    		newHead = temp;
    	}
    	
    	return new ListNode[] {newHead, head};
    }
	
    public ListNode reverseKGroup2(ListNode head, int k) {
        if (head == null)
            return head;    
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        head = dummyHead;
        while (head.next != null) {
            ListNode tail = head;
            for (int i = 1; i <= k; i++) {
                tail = tail.next;
                if (tail == null)
                    break;
            }
            if (tail != null) {
                ListNode next = head.next;
                reverseKGroupHelper2(head, tail.next);
                head = next;
                                // ListNode newHead = head;
                                // ListNode nextHead = head.next;
                                // ListNode newTail = head.next;
                                // for (int i = 1; i <= k; i++) {
                                //         ListNode temp = nextHead.next;
                                //         nextHead.next = newHead;
                                //         newHead = nextHead;
                                //         nextHead = temp;
                                // }
                                // newTail.next = nextHead;
                                // head.next = newHead;
                                // head = newTail;
            }
            else {
                break;
            }
        }  
        return dummyHead.next;
    }  
    
    private void reverseKGroupHelper2(ListNode start, ListNode end) {
        ListNode pre = start;
        ListNode cur = start.next;
        while (cur != end) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
        }
        start.next.next = end;
        start.next = pre;
    }    
	
	public static <T extends Comparable<? super T>> Node<T> reverseKGroup(
			Node<T> head, int k) {
		Node<T> dummyNode = new Node<T>();
		dummyNode.next = head;

		head = dummyNode;
		while (head.next != null) {
			Node<T> tail = head;
			for (int i = 1; i <= k; i++) {
				tail = tail.next;
				if (tail == null) {
					break;
				}
			}
			if (tail != null) {
				Node<T> newHead = head;
				Node<T> nextHead = head.next;
				Node<T> newTail = head.next;
				for (int i = 1; i <= k; i++) {
					// Node<T> stopNode = tail.next;
					// while (nextHead != stopNode) {
					Node<T> temp = nextHead.next;
					nextHead.next = newHead;
					newHead = nextHead;
					nextHead = temp;
				}
				newTail.next = nextHead;
				head.next = newHead;
				head = newTail;
			} else {
				break;
			}
		}

		return dummyNode.next;
	}

	/**
	Swap Nodes in PairsFeb 15 '121178 / 2679

	Given a linked list, swap every two adjacent nodes and return its head.

	For example,
	Given 1->2->3->4, you should return the list as 2->1->4->3.

	Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
	 */
	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public ListNode swapPairs(ListNode head) {
		ListNode dummyNode = new ListNode(-1);
		dummyNode.next = head;
		head = dummyNode;
		while (head.next != null && head.next.next != null) {
			ListNode first = head.next;
			ListNode second = head.next.next;
			first.next = second.next;
			second.next = first;
			head.next = second;
			head = first;
		}

		return dummyNode.next;
	}

	/**
	 * 
	 */
	public ReverseLinkedList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> head = new Node<Integer>(1, new Node<Integer>(2,
				new Node<Integer>(3, new Node<Integer>(4, new Node<Integer>(5,
						null)))));

		PrintUtils.printLinkedList(head);
		PrintUtils.printLinkedList(head = reverseKGroup(head, 2));
		// PrintUtils.printLinkedList(head = reverseLinkedListIterative(head));
		// PrintUtils.printLinkedList(reverseLinkedListRecursive(head));
	}

}
